package insert_sort
import (
	"common"
)

func Sort(arr []int)  {
	N := len(arr)
	for i := 1; i < N; i++ {
		for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
			common.Exch(arr, j, j-1)
		}
	}
}

func Sort1(arr []int)  {
	N := len(arr)
	for i := 1; i < N; i++ {
		min := -1
		for j := i; j > 0 && arr[i] < arr[j-1]; j-- {
			min = j-1
		}
		if min != -1 {
			temp := arr[i]
			copy(arr[min+1:i+1], arr[min:i])
			arr[min] = temp
		}
	}
}

